from cmath import inf
from typing import List


class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        if n == 1:
            return maxHeights[0]
        pre = [0] * (n + 1)
        stack = [-1]
        sum1 = 0
        for i in range(n):
            while len(stack) > 1 and maxHeights[i] <= maxHeights[stack[-1]]:
                j = stack.pop()
                sum1 -= maxHeights[j] * (j - stack[-1])
            sum1 += maxHeights[i] * (i - stack[-1])
            stack.append(i)
            pre[i] = sum1

        suf = [0] * (n + 1)
        stack = [n]
        sum1 = 0
        for i in range(n)[::-1]:
            while len(stack) > 1 and maxHeights[i] <= maxHeights[stack[-1]]:
                j = stack.pop()
                sum1 -= maxHeights[j] * (stack[-1] - j)
            sum1 += maxHeights[i] * (stack[-1] - i)
            stack.append(i)
            suf[i] = sum1
        ans = 0
        for i in range(n - 1):
            ans = max(ans, pre[i] + suf[i + 1])
        return ans


if __name__ == "__main__":
    s = Solution()
